package LeetCode.leetcode105;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //为空
        if (preorder.length == 0)
            return null;
        int divide = preorder[0];
        TreeNode root = new TreeNode(divide);
        //如果只有一个节点直接返回
        if (preorder.length == 1)
            return root;
        //在前序遍历中寻找分界位置
        int divideIndex = 0;
        for (; divideIndex < inorder.length; divideIndex++) {
            if (inorder[divideIndex] == divide)
                break;
        }
        int[] inorderLeft = new int[divideIndex];
        int[] preorderLeft = new int[divideIndex];
        //左边的两个
        for (int i = 0; i < divideIndex; i++) {
            inorderLeft[i] = inorder[i];
        }
        for (int i = 1, j = 0; i < divideIndex + 1; i++, j++) {
            preorderLeft[j] = preorder[i];
        }

        //右边
        int[] inorderRight = new int[inorder.length - divideIndex - 1];
        int[] preorderRight = new int[inorder.length - divideIndex - 1];
        for (int i = divideIndex + 1, j = 0; i < inorder.length; i++, j++) {
            inorderRight[j] = inorder[i];
        }
        for (int i = divideIndex + 1, j = 0; i < preorder.length; i++, j++) {
            preorderRight[j] = preorder[i];
        }
        //左边递归
        root.left = buildTree(preorderLeft, inorderLeft);
        //右边递归
        root.right = buildTree(preorderRight, inorderRight);
        return root;
    }
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        return test(preorder,inorder,0,inorder.length-1,0);
//    }
//    public static TreeNode test(int[] preOrder, int[] inorder, int l , int r, int index){
//        if (l < r){
//            TreeNode root = new TreeNode(preOrder[index]);
//            int pivot = 0;
//            for (int i = 0; i < inorder.length; i++) {
//                if (preOrder[index] == inorder[i]){
//                    pivot = i;
//                }
//            }
//            root.left = test(preOrder,inorder,l,pivot-1,index+1);
//            root.right = test(preOrder,inorder,pivot+1,r,index+1);
//            return root;
//        }
//        return null;
//    }
}
